import copy


class Solution(object):
    def pacificAtlantic(self, heights):
        """
        :type heights: List[List[int]]
        :rtype: List[List[int]]
        """
        m = len(heights)
        n = len(heights[0])
        DP_a = [[0 for _ in range(n)] for _ in range(m)]
        DP_p = copy.deepcopy(DP_a)
        now_set = set()
        for i in range(m):
            DP_p[i][0] = 1
            now_set.add((i, 0))
        for j in range(n):
            DP_p[0][j] = 1
            now_set.add((0, j))

        def find_p(x, y):
            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= ux < m and 0 <= uy < n:
                    if not DP_p[ux][uy] and heights[ux][uy] >= heights[x][y]:
                        DP_p[ux][uy] = 1
                        next_set.add((ux, uy))

        while now_set:
            next_set = set()
            for x, y in now_set:
                find_p(x, y)
            now_set = next_set

        now_set = set()
        for i in range(m):
            DP_a[i][-1] = 1
            now_set.add((i, n - 1))
        for j in range(n):
            DP_a[-1][j] = 1
            now_set.add((m - 1, j))

        def find_a(x, y):
            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= ux < m and 0 <= uy < n:
                    if not DP_a[ux][uy] and heights[ux][uy] >= heights[x][y]:
                        DP_a[ux][uy] = 1
                        next_set.add((ux, uy))

        while now_set:
            next_set = set()
            for x, y in now_set:
                find_a(x, y)
            now_set = next_set

        out = []
        for i in range(m):
            for j in range(n):
                if DP_a[i][j] and DP_p[i][j]:
                    out.append([i, j])
        return out


data = Solution()
heights = [[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]
print(data.pacificAtlantic(heights))
heights = [[2, 1], [1, 2]]
print(data.pacificAtlantic(heights))
heights = [[2]]
print(data.pacificAtlantic(heights))
heights = [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
print(data.pacificAtlantic(heights))
